package com.gorkr.labuladong.data_struct.bst;

import org.junit.jupiter.api.Test;

/**
 * 中序遍历有序
 *
 * 全局变量 让递归的时候 能保存共享内容 记录每一次递归的变化啥的
 * @author gorkr
 * @date 2022/08/07 10:03
 **/
public class M36ErCHaSouSuoShuYuShuangXiangLianBiaoIcof {
    class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val,Node _left,Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    }
    private Node head, pre;

    public Node treeToDoublyList(Node root) {
        if(root==null){
            return null;
        }

        dfs(root);
        head.left = pre;
        pre.right = head;

        return head;
    }


    private void dfs(Node root){


        if(root==null){
            return ;
        }

        dfs(root.left);
        // 访问的不是头节点
        if(pre!=null){
            pre.right = root;

        }else {
            // root是头节点
            head = root;
        }
        root.left = pre;
        pre = root;

        // 中序
        dfs(root.right);
    }

    @Test
    public void test(){

        Node root = new Node(4);
        root.right = new Node(5);
        root.left = new Node(2);
        root.left.left = new Node(1);
        root.left.right = new Node(3);

    }


}
    